package com.davidlife.javase.datatype;

public class BinarySearch {

	public static void main(String[] args) {
		int[] arr = {3, 5, 6, 7, 8, 9, 11};
		System.out.println("普通循环二分法：" + binarySearch(arr, 1));
		System.out.println("递归二分法：" + binarySearchByRecursion(arr, 0, arr.length-1, 1));
	}
	
	/**
	 * 二分法查找前提是数组是已排好序的
	 * 二分法查找的时间复杂度O(logn)。
	 * 
	 */
	public static int binarySearch(int[] arr, int key) {
		int low = 0;
		int high = arr.length - 1;
		while(low <= high) {
			int mid = (low + high) >>> 1;
			int midVal = arr[mid];
			if(midVal < key) 
				low = mid + 1;
			else if(midVal > key)
				high = mid - 1;
			else
				return mid;
		}
		return -1;
	}
	
	/**
	 * 递归实现的二分法查找
	 * @param arr
	 * @param low
	 * @param high
	 * @param key
	 * @return
	 */
	public static int binarySearchByRecursion(int[] arr, int low, int high, int key) {
		if(low > high) return -1;
		int mid = (low + high) >>> 1;
		int midVal = arr[mid];
		if(midVal < key)
			return binarySearchByRecursion(arr, mid+1, high, key);
		else if(midVal > key)
			return binarySearchByRecursion(arr, low, mid-1, key);
		else
			return mid;
	}
}
